from collections import deque


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return str(self.val)



def built_tree_by_complete_tree(arr):
    '''
    :param arr: 数组表示的完全二叉树
    :return: 返回树的根节点
    '''
    if not arr: return None
    n = len(arr)
    def build(root, i):
        left_idx = i * 2 + 1
        if left_idx < n and arr[left_idx]:
            root.left = TreeNode(arr[left_idx])
            build(root.left, left_idx)
        if left_idx + 1 < n and arr[left_idx + 1]:
            root.right = TreeNode(arr[left_idx + 1])
            build(root.right, left_idx + 1)
        return root
    return build(TreeNode(arr[0]), 0)


def preorder(root):
    if not root: return
    print(root.val, end=" ")
    preorder(root.left)
    preorder(root.right)

def inorder(root):
    if not root: return
    inorder(root.left)
    print(root.val, end=" ")
    inorder(root.right)

def postorder(root):
    if not root: return
    postorder(root.left)
    postorder(root.right)
    print(root.val, end=" ")

def leveloder(root):
        if not root: return []
        q = deque([root])
        res = []
        while q:
            level = []
            level_size = len(q)
            for i in range(level_size):
                cur = q.popleft()
                if cur:
                    level.append(str(cur.val))
                    q.append(cur.left)
                    q.append(cur.right)
                else:
                    level.append('#')
            res.append(level)
        print(res)


if __name__ == '__main__':
    arr = [3,9,20,None,None,15,7]
    root = built_tree_by_complete_tree(arr)
    preorder(root)
    print()
    inorder(root)
    print()
    postorder(root)
    print()
    leveloder(root)
